The present invention relates generally to rasterizers and, more particularly, to optimizing results during the conversion of primitives defined by vertexes to equivalent images composed of pixel patterns that can be stored and manipulated as sets of bits.
Raster displays are commonly used in computer graphics systems. These displays store graphics images as a matrix of picture elements or xe2x80x9cpixelsxe2x80x9d with data representing each pixel being stored in a display buffer. This data specifies the display attributes for each pixel on the screen such as the intensity and color of the pixel. An entire image is read from the display buffer and displayed on the screen by sequentially scanning out horizontal rows of pixel data or xe2x80x9cscan lines.xe2x80x9d
Raster display systems commonly use polygons as basic building blocks or xe2x80x9cprimitivesxe2x80x9d for drawing more complex images. Triangles are a common basic primitive for polygon drawing systems, since a triangle is the simplest polygon and more complex polygons can always be represented as sets of triangles. The process of drawing triangles and other geometric primitives on the screen is known as xe2x80x9crasterization.xe2x80x9d
An important part of rasterization involves determining which pixels fall within a given triangle. Rasterization systems generally step from pixel to pixel in various ways and determine whether or not to xe2x80x9crender,xe2x80x9d i.e. draw into a frame buffer or pixel map, each pixel as part of the triangle. This, in turn, determines how to set the data in the display buffer representing each pixel. Various traversal algorithms have been developed for moving from pixel to pixel in a way such that all pixels within the triangle are covered.
Rasterization systems sometimes represent a triangle as a set of three edge-functions. An edge function is a line equation representing a straight line, which serves to subdivide a two-dimensional plane. Edge functions classify each point within the plane as falling into one of three regions: the region xe2x80x9cinsidexe2x80x9d of the triangle, the region xe2x80x9coutsidexe2x80x9d of the triangle, or the region representing a line itself. The type of edge function that will be discussed has the property that points xe2x80x9cinsidexe2x80x9d of the triangle have a value greater than zero, points xe2x80x9coutsidexe2x80x9d have a value less than zero, and points exactly on the line have a value of zero. This is shown in Prior Art FIG. 1. Applied to rasterization systems, the two-dimensional plane is represented by the graphics screen, points are represented by individual pixels, and the edge function serves to subdivide the graphics screen.
Triangles are created by the union of three edges, or more particularly three half-planes, each of which is specified by edge functions. It is possible to define more complex polygons by using Boolean combinations of more than three edges. Since the rasterization of triangles involves determining which pixels to render, a tie-breaker rule is generally applied to pixels that lie exactly on any of the edges to determine whether the pixels are to be considered interior or exterior to the triangle.
As shown in Prior Art FIG. 1A, each pixel has associated with it a set of edge variables, (e0, e1 and e2), which are proportional to the signed distance between the pixel and the three respective edges. The value of each edge variable is determined for a given triangle by evaluating the three edge functions, f0 (x,y), f1 (x,y) and f2 (x,y) for the pixel location. It is important to note that it can be determined whether or not a pixel falls within a triangle by looking at only the signs of e0, e1 and e2.
In determining which pixels to render within a triangle, typical rasterization systems compute the values of the edge variables, (e0, e1 and e2), for a given set of three edge functions and a given pixel position, and then use a set of increment values (xcex94eoutside, xcex94einside, etc.) to determine the edge variable values for adjacent pixels. The rasterization system traverses the triangle, adding the increment values to the current values as a traversal algorithm steps from pixel to pixel.
With reference again to Prior Art FIG. 1, a line is illustrated that is defined by two points: (X,Y) and (X+dX,Y+dY). As noted above, this line can be used to divide the two dimensional space into three regions: all points xe2x80x9coutsidexe2x80x9d of, xe2x80x9cinsidexe2x80x9d of, and exactly on the line.
The edge f(x,y) can be defined as:
xe2x80x83f(x,y)=(xxe2x88x92X)dYxe2x88x92(yxe2x88x92Y)dX.
This function has the useful property that its value is related to the position of the point (x,y) relative to the edge defined by the points (X,Y) and (X+dX, Y+dY):
f(x,y) greater than 0 if (x,y) is xe2x80x9cinsidexe2x80x9d;
f(x,y)=0 if (x,y) is exactly on the line; and
f(x,y) less than 0 if (x,y) is xe2x80x9coutsidexe2x80x9d.
Existing rasterization systems commonly use this function, since it can be computed incrementally by simple addition:
f(x+1,y)=f(x,y)+dY; and
f(x,y+1)=f(x,y)xe2x88x92dX.
A variety of different traversal algorithms are presently used by different rasterization systems in the rendering process. Any algorithm guaranteed to cover all of the pixels within the triangle can be used.
For example, some solutions involve generating the pixels in a unidirectional manner. Such traditional unidirectional solution includes generating the pixels row-by-row in a constant direction. This requires that the sequence shift across the primitive to a starting location on a first side of the primitive upon finishing at a location on an opposite side of the primitive. Each time this shift is executed, pixels or texture values are stored which were not positioned adjacent to pixels or texture values processed immediately beforehand. Therefore, such distant pixels or texture values have a greater chance of belonging to different memory access blocks, making such access inefficient.
This problem is exacerbated with primitives of a large size. For example, if a sequence generates pixels along a very long row or column, the probability is reduced that contiguous pixels or texture values from an adjacent row or column, respectively, will still be in memory. This probability is further reduced with memory of a limited size.
As yet another example, a haphazard generation sequence includes jumping around randomly within the primitive. Using this method, pixels or texture values that are accessed are rarely adjacent to those that were accessed recently enough to still be in a limited size memory.
There is therefore a need for a rasterization system that processes pixels or texture values that are frequently adjacent to pixels or texture values that have been previously processed immediately beforehand and are still stored in memory.
A method, apparatus and article of manufacture are provided for performing rasterization using alternating sense point traversal. Upon receipt of a primitive, i.e. a triangle, a plurality of points is positioned on or near the primitive. Such points define an enclosed convex region and are located at corners of the convex region. In operation, the points and thus the convex region are moved in an alternating manner for the purpose of identifying an area in the primitive for rendering pixels therein. In particular, the points are moved in a boustrophedonic manner.
This boustrophedonic rasterization constrains the sequence to obey certain rules that offer better performance for hardware. Boustrophedonic refers to a serpentine pattern that folds back and forth. A horizontal boustrophedonic sequence, for example, may generate all the pixels within a primitive triangle that are on one row from left to right, and then generate the next row right to left, and so on. Such a folded path ensures that an average distance from a generated pixel to recently previously generated pixels is relatively small.
Generating pixels that are near recently generated pixels is important when recent groups of pixels and/or their corresponding texture values are kept in memories of a limited size. The boustrophedonic sequence more often finds the pixels or texture values already loaded into such memories, and therefore repeating the memory load occurs less often.
In one embodiment, at least one boundary may be used which divides the primitive into a plurality of portions. In operation, the polygon-defining points may be moved in each of the portions separately. Further, the points may be moved through an entirety of a first one of the portions before being moved in a second one of the portions. As an option, the boundary spacing may be defined based on a memory size and the size of the smallest texture element, a xe2x80x9ctexel.xe2x80x9d
Rasterization with boundaries is another constraint on the pixel generation sequence that is complementary to boustrophedonic rasterization. If a primitive is very wide, the pixels of a single row may not fit in a limited-size memory. Rasterization with boundaries divides the triangle into limited-width rows (or columns), and generates all the pixels within such a portion before moving on to the next portion.